/**
 * 42. 接雨水
 *
 * 【困难】
 *
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 * 示例 1：
 * https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/22/rainwatertrap.png
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 *
 * 示例 2：
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 */

/**
 * 算法思路
 * 逐个计算每一列能存下的水量。
 */

// type TrapType = (height: number[]) => number

interface TrapType {
	(height: number[]): number
}

let trap: TrapType
/**
 * 暴力法
 */
trap = function trap(height) {
	let ans = 0
	const len = height.length

	for (let i = 0; i < len; i++) {
		let leftMax = 0
		for (let j = 0; j <= i; j++) {
			if (height[j] >= leftMax) {
				leftMax = height[j]
			}
		}

		let rightMax = 0
		for (let k = i; k < len; k++) {
			if (height[k] >= rightMax) {
				rightMax = height[k]
			}
		}

		ans += Math.min(leftMax, rightMax) - height[i]
	}

	return ans
}

/**
 * 双指针
 */
trap = (height) => {
	let ans = 0
	const len = height.length

	const leftMax: number[] = []
	leftMax[0] = height[0]
	for (let i = 1; i < len; i++) {
		leftMax[i] = Math.max(leftMax[i - 1], height[i])
	}

	const rightMax: number[] = []
	rightMax[len - 1] = height[len - 1]
	for (let i = len - 2; i >= 0; i--) {
		rightMax[i] = Math.max(rightMax[i + 1], height[i])
	}

	for (let i = 0; i < len; i++) {
		ans += Math.min(leftMax[i], rightMax[i]) - height[i]
	}

	return ans
}

/**
 * 双指针优化
 */
trap = (height) => {
	let ans = 0
	let len = height.length

	let left = 0
	let leftMax = 0

	let right = len - 1
	let rightMax = 0

	while (left <= right) {
		leftMax = Math.max(leftMax, height[left])
		rightMax = Math.max(rightMax, height[right])
	}

	if (leftMax < rightMax) {
		ans += leftMax - height[left++]
	} else if (leftMax > rightMax) {
		ans += rightMax - height[right--]
	} else {
		ans += leftMax - height[left++]

		if (left <= right) {
			ans += rightMax - height[right--]
		}
	}

	return ans
}
